package class02;

import java.util.Stack;

/**
 * 采用栈结构是最方便的的，但是有额外的空间申请
 * 采用有限变量，先找到中间位置，如果书偶数则找到上中点位置，然后反转右半部分；分别从左右临界点遍历是否相等，左右的next 指针有一个为null  遍历完毕；将遍历结果返回并且还原右半部分
 */
public class Code02_IsPalindromeList {
    static class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
        }
    }

    // need extra space
    static boolean isPalindrome1(Node head) {
        if (null == head || null == head.next) {
            return true;
        }

        Stack<Integer> stack = new Stack<>();
        Node cur = head;
        while (null != cur) {
            stack.push(cur.value);
            cur = cur.next;
        }

        while (!stack.isEmpty()) {
            if (stack.pop() != head.value) {
                return false;
            }
            head = head.next;
        }
        return true;

    }

    static boolean isPalindrome2(Node head) {
        // 1 找到中点n1
        if (null == head || null == head.next) {
            return true;
        }

        Node n1 = head;
        Node n2 = head;

        while (null != n2.next && null != n2.next.next) {
            n1 = n1.next;
            n2 = n2.next.next;
        }


        // 2.反转右部分
        Node n3 = null;
        n2 = n1.next;
        n1.next = null;
        while (null != n2) {
            n3 = n2.next;
            n2.next = n1;
            n1 = n2;
            n2 = n3;
        }


        // 3.遍历并进行等值判断
        Boolean flag = true;
        n3 = n1;// 右边节点
        n2 = head;// 左边节点
        while (null != n1 && null != n2) {
            if (n1.value != n2.value) {
                flag = false;
                break;
            }
            n1 = n1.next;
            n2 = n2.next;
        }
        // 4.还原右部分 此时n3 在最右侧
        n1 = n3.next;
        n3.next = null;
        while (null != n1) {
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
        }

        return flag;
    }

    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head = null;
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");

        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");

        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");

        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");

        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");

        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");

        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");

        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(2);
        head.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");

        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(2);
        head.next.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");

        printLinkedList(head);
        System.out.println("=========================");

    }

}
